package com.leetcode.partition1;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/9/9 18:36
 */
public class LC15三数之和 {

    public static List<List<Integer>> threeSum(int[] nums) {
//        return hashtable(nums);
//        List<List<Integer>> answers = new ArrayList<>();
//        Arrays.sort(nums);
//        backtracking(answers, new HashSet<>(), new ArrayList<>(), 0, nums, 0);
//        return answers;
        return doublePointer(nums);
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println(threeSum(nums));
    }

    private static List<List<Integer>> doublePointer(final int[] nums) {
        List<List<Integer>> answers = new ArrayList<>();
        Arrays.sort(nums);
        //第一层for循环负责选取第一个元素
        for (int i = 0; i < nums.length; i++) {
            //经排序后，如果选出来的第一个元素都大于0，就没有必要以当前元素为第一个元素进行选取
            if (nums[i] > 0) return answers;
            //对第一个元素进行去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            //选取第二个元素和第三个元素
            int left = i + 1, right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                //如果当前三数之和的结果大于0，说明right太大，需要减小；如果sum小于0，说明left太小，需要扩大；如果刚好等于0，就是一个需要
                //求得的结果，添加到集合中并继续寻找下一组，同时，left和right依然需要去重
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    answers.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    left++;
                    right--;
                }
            }
        }
        return answers;
    }

    private static void backtracking(List<List<Integer>> answers, Set<Integer> startSet, List<Integer> path, int sum, final int[] nums, int startIndex) {
        if (path.size() == 3) {
            if (sum == 0 && !answers.contains(path)) {
                startSet.add(path.get(0));              //将第一个元素存放，如果后面开始的第一个元素在startSet中存在，则进行剪枝
                answers.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            if ((path.size() == 0 && nums[i] > 0) || startSet.contains(nums[i])) continue;
            path.add(nums[i]);
            backtracking(answers, startSet, path, sum + nums[i], nums, i + 1);
            path.remove(path.size() - 1);
        }
    }

    private static List<List<Integer>> hashtable(final int[] nums) {
        List<List<Integer>> answers = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) return answers;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            Set<Integer> ht = new HashSet<>();

            //j记录第二个元素的下标，使用哈希表来寻找第三个元素
            for (int j = i + 1; j < nums.length; j++) {
                //第二个元素的去重
                if (j > i + 2 && nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2]) continue;
                //计算出第三个元素，如果第三个元素在哈希表中出现过，则nums[i]、nums[j]、和k能构成三数之和
                int k = -(nums[i] + nums[j]);
                if (ht.contains(k)) {
                    answers.add(Arrays.asList(nums[i], nums[j], k));
                    ht.remove(k);
                    continue;
                }
                ht.add(nums[j]);
            }
        }
        return answers;
    }
}
